package com.leetcode.贪心;

/**
 * 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度
 * 判断你是否能够到达最后一个下标。
 * @author LZF
 *
 */
public class L55跳跃游戏 {
	/**
	 * 每一个元素能跳到的最远下标是i+nums[i],只要是在i+nums[i]这个范围内的所有位置都可以跳到
	 * 首先先设置max表示能跳到的最远下标。
	 * 在max的范围内，计算每个位置所能跳到的最远下标，然后更新max，只要max >= nums.length - 1
	 * 则表示能跳到
	 * @param nums
	 * @return
	 */
	public boolean canJump(int[] nums) {
        if(nums.length == 1) return true;
        int max = nums[0];
        for(int i = 1;i < nums.length;i++){
            if(max >= nums.length - 1) return true;
            if(i <= max){
                max = Math.max(max,i + nums[i]);
            } else {
                return false;
            }
        }
        return false;
    }
}
